package algorithm;

import java.util.*;

public class BinaryTree2 {


    //二叉树的递归套路：二叉树的递归序（每个节点要访问3次） + 左右两树返回什么信息 + 是否需要考虑当前节点 + 最后返回自己的信息

    public static class Node{
        public Node left;
        public Node right;
        public int value;
        public Node (int value){
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

    public static class Employee{
        public int happy;
        public List<Employee> nexts;

        public Employee(int h){
            happy = h;
            nexts = new ArrayList<>();
        }
    }

//平衡树的判断============================================================================

    public static boolean isBalanced1(Node head){
        if(head == null)
            return true;
        boolean[] ans = new boolean[]{true};
        process1(head, ans);
        return ans[0];
    }

    public static int process1(Node head, boolean[] ans){
        if(head ==  null || ans[0] == false)
            return 0;
        int leftHeight = process1(head.left, ans);
        int rightHeight = process1(head.right, ans);
        if(Math.abs(leftHeight - rightHeight)>1){
            ans[0] = false;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public static class Info{
        public boolean isBalance;
        public int height;

        public Info(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

    public static boolean isBalanced2(Node head){
        Info info = process2(head);
        return info.isBalance;
    }

    public static Info process2(Node head){
        if(head == null){
            return new Info(true, 0);
        }

        Info leftInfo = process2(head.left);
        Info rightInfo = process2(head.right);
        int max = Math.max(leftInfo.height, rightInfo.height)+1;
        if(!leftInfo.isBalance || !rightInfo.isBalance || Math.abs(leftInfo.height-rightInfo.height)>1){
            return new Info(false, max);
        }
        return new Info(true, max);
    }


//判断是否是满二叉树=================================================================================================

    public static class Info2{
        public int nodes;
        public int height;

        public Info2(int nodes, int height) {
            this.nodes = nodes;
            this.height = height;
        }
    }

    public static boolean isFull(Node head){
        if(head == null)
            return true;
        Info2 info = isFullProcess(head);
        if((1<<info.height)-1 == info.nodes)
            return true;
        return false;
    }

    public static Info2 isFullProcess(Node head){

        if(head == null)
            return new Info2(0, 0);

        Info2 leftInfo = isFullProcess(head.left);
        Info2 rightInfo = isFullProcess(head.right);
        int height = Math.max(leftInfo.height, rightInfo.height)+1;
        return new Info2(leftInfo.nodes + rightInfo.nodes + 1, height);

    }

//判断是否是搜索二叉树==============================================================================

    public static class Info3{
        public boolean isBST;
        public int max;
        public int min;

        public Info3(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public static boolean isBST(Node head){
        if(head == null)
            return true;
        Info3 info = isBSTProcess(head);
        return info.isBST;
    }

    public static Info3 isBSTProcess(Node head){
        if(head == null)
            return null;

        Info3 leftInfo = isBSTProcess(head.left);
        Info3 rightInfo = isBSTProcess(head.right);

        int max = head.value;
        int min = head.value;

        boolean isBST = true;
        if(leftInfo != null){
            isBST = leftInfo.isBST? (leftInfo.max< head.value? true: false) : false;
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        if(rightInfo != null){
            if(isBST)
                isBST = rightInfo.isBST? (rightInfo.min> head.value? true: false) : false;
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }

        return new Info3(isBST, max, min);
    }

    public static boolean isBST1(Node head) {
        if (head == null) {
            return true;
        }
        ArrayList<Node> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).value <= arr.get(i - 1).value) {
                return false;
            }
        }
        return true;
    }

    public static void in(Node head, ArrayList<Node> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }


//返回最大搜索二叉树的头结点======================================================================
    public static class Info4{
        public boolean isBST;
        public int max;
        public int min;
        public int size_max;
        public Node subBST;


    public Info4(boolean isBST, int max, int min, int size_max, Node subBST) {
        this.isBST = isBST;
        this.max = max;
        this.min = min;
        this.size_max = size_max;
        this.subBST = subBST;
    }
    }

    public static Node maxSubBST(Node head){
        if(head == null)
            return null;
        Info4 info4 = maxSubBSTProcess(head);
        return info4.subBST;
    }

    public static Info4 maxSubBSTProcess(Node head){
        if(head == null)
            return  null;

        Info4 leftInfo = maxSubBSTProcess(head.left);
        Info4 rightInfo = maxSubBSTProcess(head.right);

        int max = head.value;
        int min = head.value;
        boolean isBST = true;
        int size_max = 0;
        Node subBST = head;

        if(leftInfo != null){
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            isBST = false;
            size_max = leftInfo.size_max;
            subBST = leftInfo.subBST;
        }
        if(rightInfo != null){
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            isBST = false;
            if(size_max < rightInfo.size_max){
                size_max = rightInfo.size_max;
                subBST = rightInfo.subBST;
            }
        }

        if((leftInfo == null? true : (leftInfo.isBST? leftInfo.max < head.value : false)) &&
                (rightInfo == null? true : (rightInfo.isBST? rightInfo.min > head.value : false))){
            isBST = true;
            size_max = (leftInfo == null? 0 : leftInfo.size_max) +
                    (rightInfo == null? 0 : rightInfo.size_max) + 1;
            subBST = head;
        }

        return new Info4(isBST, max, min, size_max, subBST);
    }


//判断是否是完全二叉树========================================================================

    public static class Info5{
        public boolean isCBT;
        public boolean isFull;
        public int height;

        public Info5(boolean isCBT, boolean isFull, int height) {
            this.isCBT = isCBT;
            this.isFull = isFull;
            this.height = height;
        }
    }

    public static boolean isCBT(Node head){
        if(head == null)
            return true;
        Info5 info5 = isCBTProcess(head);
        return info5.isCBT;
    }

    public static Info5 isCBTProcess(Node head){
        if(head == null)
            return new Info5(true, true, 0);

        Info5 leftInfo = isCBTProcess(head.left);
        Info5 rightInfo = isCBTProcess(head.right);

        boolean isCBT = false;
        boolean isFull = false;
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        if(leftInfo.isCBT && rightInfo.isFull && leftInfo.height - 1 == rightInfo.height){
            isCBT = true;
        }
        if(leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height)
            isCBT = true;
        if(leftInfo.isFull && rightInfo.isFull && leftInfo.height - rightInfo.height == 1){
            isCBT = true;
        }
        if(leftInfo.isFull && rightInfo.isFull && leftInfo.height - rightInfo.height == 0){
            isCBT = true;
            isFull = true;
        }

        return new Info5(isCBT, isFull, height);
    }

    public static boolean isCBT2(Node head){
        if(head == null)
            return true;
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        boolean isNoFull = false;
        while(!queue.isEmpty()){
            Node poll = queue.poll();
            if(poll.left != null)
                queue.add(poll.left);
            if(poll.right != null)
                queue.add(poll.right);
            if(!isNoFull && (poll.left == null || poll.right == null)){
                isNoFull = true;
                if(poll.left == null && poll.right != null)
                    return false;
                continue;
            }
            if(isNoFull && (poll.left != null || poll.right != null))
                return false;
        }
        return true;
    }


//最大距离===================================================================================

    public static class Info6{
        public int maxDistance;
        public int height;

        public Info6(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }

    public static int maxDistance(Node head){
        if(head == null)
            return 0;
        Info6 info6 = maxDistanceProcess(head);
        return info6.maxDistance;
    }

    public static Info6 maxDistanceProcess(Node head){
        if(head == null)
            return new Info6(0, 0);

        Info6 leftInfo = maxDistanceProcess(head.left);
        Info6 rightInfo = maxDistanceProcess(head.right);

        int maxDistance = Math.max(leftInfo.maxDistance, rightInfo.maxDistance);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        if(maxDistance > leftInfo.height + rightInfo.height + 1)
            return new Info6(maxDistance, height);
        else
            return new Info6(leftInfo.height + rightInfo.height + 1, height);

    }


//最大快乐值============================================================================

    public static class Info7{
        public int yes;
        public int no;

        public Info7(int yes, int no) {
            this.yes = yes;
            this.no = no;
        }
    }

    public static int maxHappy(Employee employee){
        if(employee == null)
            return 0;
        Info7 info7 = maxHappyProcess(employee);
        return Math.max(info7.no, info7.yes);
    }

    public static Info7 maxHappyProcess(Employee employee){
        if(employee.nexts.isEmpty())
            return new Info7(employee.happy, 0);

        int yes = employee.happy;
        int no = 0;
        for (Employee next : employee.nexts) {
            Info7 nextInfo = maxHappyProcess(next);
            yes += nextInfo.no;
            no += Math.max(nextInfo.no, nextInfo.yes);
        }
        return new Info7(yes, no);
    }

//最低公共祖先==============================================================================

    public static class Info8{
        public Node ans;
        public boolean findO1;
        public boolean findO2;

        public Info8(Node ans, boolean findO1, boolean findO2) {
            this.ans = ans;
            this.findO1 = findO1;
            this.findO2 = findO2;
        }
    }

    public static Node lowestAncestor(Node head, Node o1, Node o2){
        if(head == null)
            return null;
        Info8 info8 = lowestAncestorProcess(head, o1, o2);
        return info8.ans;
    }

    public static Info8 lowestAncestorProcess(Node head, Node o1, Node o2){
        if(head == null)
            return new Info8(null, false,false);

        Info8 leftinfo = lowestAncestorProcess(head.left, o1, o2);
        Info8 rightInfo = lowestAncestorProcess(head.right, o1, o2);

        boolean findO1 = false;
        boolean findO2 = false;
        Node ans = null;

        if(leftinfo.ans != null || rightInfo.ans != null){
            return new Info8(leftinfo.ans == null? rightInfo.ans : leftinfo.ans, true, true);
        }
        if(leftinfo.findO1 || rightInfo.findO1 || head == o1)
            findO1 = true;
        if(leftinfo.findO2 || rightInfo.findO2 || head == o2)
            findO2 = true;
        if(findO1 && findO2)
            ans = head;
        return new Info8(ans, findO1, findO2);
    }

    public static Node lowestAncestor2(Node head, Node o1, Node o2){
        if(head == null)
            return null;
        HashMap<Node, Node> map = new HashMap<>();
        map.put(head, null);
        preParents(head, map);
        HashSet<Node> set = new HashSet<>();
        set.add(head);
        Node node = o1;
        while(map.get(node) != null){
            set.add(node);
            node = map.get(node);
        }
        node = o2;
        while(!set.contains(node)){
            node = map.get(node);
        }
        return node;
    }

    public static void preParents(Node head, HashMap<Node, Node> parentMap){
        if(head == null)
            return;
        if(head.left != null)
            parentMap.put(head.left, head);
        if(head.right != null)
            parentMap.put(head.right, head);
        preParents(head.left, parentMap);
        preParents(head.right, parentMap);
    }


    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    // for test
    public static Node pickRandomOne(Node head) {
        if (head == null) {
            return null;
        }
        ArrayList<Node> arr = new ArrayList<>();
        fillPrelist(head, arr);
        int randomIndex = (int) (Math.random() * arr.size());
        return arr.get(randomIndex);
    }

    // for test
    public static void fillPrelist(Node head, ArrayList<Node> arr) {
        if (head == null) {
            return;
        }
        arr.add(head);
        fillPrelist(head.left, arr);
        fillPrelist(head.right, arr);
    }

//    public static int getBSTSize(Node head) {
//        if (head == null) {
//            return 0;
//        }
//        ArrayList<Node> arr = new ArrayList<>();
//        inBST(head, arr);
//        for (int i = 1; i < arr.size(); i++) {
//            if (arr.get(i).value <= arr.get(i - 1).value) {
//                return 0;
//            }
//        }
//        return arr.size();
//    }
//
//    public static void inBST(Node head, ArrayList<Node> arr) {
//        if (head == null) {
//            return;
//        }
//        inBST(head.left, arr);
//        arr.add(head);
//        inBST(head.right, arr);
//    }
//
//    public static Node maxSubBSTHead1(Node head) {
//        if (head == null) {
//            return null;
//        }
//        if (getBSTSize(head) != 0) {
//            return head;
//        }
//        Node leftAns = maxSubBSTHead1(head.left);
//        Node rightAns = maxSubBSTHead1(head.right);
//        return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
//    }


    public static void main(String[] args) {
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            Node o1 = pickRandomOne(head);
            Node o2 = pickRandomOne(head);
            if (lowestAncestor(head, o1, o2) != lowestAncestor2(head, o1, o2)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}
